A cyclic redundancy check is commonly performed on a stream of data to detect errors. A CRC-enabled device calculates a CRC code for a block of data prior to transmission, and if the CRC code calculated at the receiver does not match the code calculated at the transmitter, an error will have occurred.
FIG. 1a shows a typical CRC code, which is known as a CRC-32 IEEE 802.3 polynomial. These features may vary from one standard to another. The specific CRC polynomial is given for illustrative purposes only, and it will be understood that other forms of CRC polynomial may be employed. The CRC-32 IEEE 802.3 polynomial is written as follows:x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1
Another common representation of the of the CRC writes the corresponding polynomial coefficients as follows:0x04C11DB7
The polynomial and the calculation required to arrive at a CRC are clearly defined in the standard, but no means of implementation is specified. The CRC-32 which is part of the standard is defined according to the following equation:CRC=complement remainder of ((M(x)*x32)/G(x))
It should be noted that the complement step is specific to this particular standard.
FIG. 1b shows a prior art implementation 110 of an apparatus for calculating a CRC-32 using a Linear Feedback Shift Register (LFSR) circuit, which produces the required result. The message is shifted one bit at a time, and the final CRC is the 32 bits remaining in registers R0 through R31 after completely processing the message. This circuit is not suitable for use with high-speed data due to the limitations of integrated circuit technology. Likewise, a software implementation of the LFSR function cannot keep up with the incoming data at high rates.
Much has been written about the mathematics, which describe the process by which a particular CRC calculation provides reliable error detection properties, and it will not be repeated here. In addition, the mathematical nature of the binary Galois Field GF(2),m, which is used in the calculation process is well known. The relevant information is contained in the following references, the contents of which are herein incorporate by reference:
W. W. Peterson, D. T. Brown; “Cyclic Codes for Error Detection”; ISSN 0096-8390; January 1961
[2] G. Campobello, G. Patane, M. Russo; “Parallel CRC Realization”; ISSN 0018-9340; October 2003
[3] IEEE Std. 802.3™ 2008, Clause 3.2.9
[4] Shieh et. al.; “A Systematic Approach for Parallel CRC Computation”; Journal of Information Science and Engineering 17; 2001
Conceptually, calculating a CRC involves passing the data serially through a Linear Feedback Shift Register (LFSR) one bit at a time where the coefficients of the CRC polynomial correspond to XOR functions on the LFSR. However, modern communication systems require a faster method of calculation, and therefore the parallel method is typically used. This method allows a CRC to be calculated on as many bits in parallel as desired using a tree of exclusive OR (XOR) gates. The arrangement of a particular XOR tree given a specific CRC polynomial and number of inputs bits has been extensively described in the prior art.